#include "graph_support/alg_correctness_tests/dinic_alg_tests/TestDinicAlgCorrectness.h"

#include <vector>
#include <time.h>

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/CollectionsInit.h"

#include "graph_support/alg/flow/Dinic.h"
#include "graph_support/alg/flow/MinCostFlow.h"

#include "graph_support/alg_correctness_tests/dinic_alg_tests/CompactNet.h"
#include "graph_support/alg_correctness_tests/dinic_alg_tests/CompactNetDinic.h"
#include "graph_support/alg_correctness_tests/dinic_alg_tests/GeneratorsCollection.h"

#include "graph_support/alg_correctness_tests/generate_graph/IGraphGenerator.h"

using namespace dinic_alg_test;
using namespace GRAPH_SUPPORT_NS::utils;
using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::alg::flow;
using namespace generate_graph;

void TestCompareStupidDinicWithOfficial()
{
	std::vector< int > vertices = arr2vector< int >(
			( const int[] ) { 0, 1, 2, 3, 4, 5 } );
	int src = 0;
	int dest = 1;
	FlowGraph2Gen vgr( vertices, true );
	CompactNet cgr( vertices.size(), 100 );

	vgr.addEdge( 0, 1, 123 );
	vgr.addEdge( 0, 2, 234 );
	vgr.addEdge( 2, 3, 234 );
	vgr.addEdge( 3, 1, 345 );
	Dinic< FlowGraph2Gen > dinic( vgr );
	dinic( src, dest );
	BOOST_CHECK_EQUAL( 357, dinic.getTotalFlow() );
	cpgr2compact( vgr, cgr );
	double stupidFlow = stupidDinicOnCompactNet( cgr, src, dest );
	BOOST_CHECK_EQUAL( 357, stupidFlow );

	cgr.clear();
	vgr.addEdge( 0, 4, 10 );
	vgr.addEdge( 4, 3, 10 );
	vgr.addEdge( 2, 5, 10 );
	vgr.addEdge( 5, 1, 10 );
	cpgr2compact( vgr, cgr );
	dinic( src, dest );
	BOOST_CHECK_EQUAL( 367, dinic.getTotalFlow() );
	stupidFlow = stupidDinicOnCompactNet( cgr, src, dest );
	BOOST_CHECK_EQUAL( 367, stupidFlow );
}

namespace
{

double theabs( double d )
{
	return d > 0 ? d : -d;
}

void runAllDinicAlgCorrectnessTest( const IGraphGeneratorPtr & generator, int & failsCount, double eps )
{
	try
	{
		IGraphGenerator::GraphPtr agrPtr = generator->generate();
		FlowGraph2Gen * grPtr = dynamic_cast< FlowGraph2Gen * >( agrPtr.get() );
		BOOST_CHECK( grPtr != NULL );
		CompactNetPtr cnptr = clonegr2compact( * grPtr );

		double stupidFlow = stupidDinicOnCompactNet( * cnptr, 0, 1, eps );
		Dinic< FlowGraph2Gen > dinic( * grPtr );
		dinic( 0, 1 );
		BOOST_CHECK_CLOSE( stupidFlow, dinic.getTotalFlow(), eps * 60 );
		if ( theabs( stupidFlow - dinic.getTotalFlow() ) > eps * 10 )
		{
			failsCount++;
		}
	} catch (...) {
		failsCount++;
	}
}

template< typename SingleTCRunnerFn >
int runAllAlgCorrectnessTests( const std::vector< TestCase >testCases, SingleTCRunnerFn runSingleTC, double eps = 1e-5 )
{
	int testCasesCount = testCases.size();
	int failsCount = 0;
	for ( int i = 0; i < testCasesCount; i++ )
	{
		IGraphGeneratorPtr generator = testCases[i].first;
		std::cout << ( i == 0 ? " " : "; " ) << generator->getName() << " (" << testCases[i].second << ")";
		std::cout.flush();
		time_t runBeg = time( NULL );
		for ( int tcr = 0; tcr < testCases[i].second; tcr++ )
		{
			runSingleTC( generator, failsCount, eps );
		}
		time_t runEnd = time( NULL );
		double runRime = runEnd - runBeg;
		if ( runRime > 1.1 )
		{
			std::cout << " (time: " << runRime << " sec.)";
		}
	}
	return failsCount;
}

}

void TestDinicAlgCorrectness()
{
	std::cout << "\tDinic algorithm correctness tests: ";
	bool enableDinicAlgCorrectnessTests = false;
#ifdef DINIC_ALG_TESTS
	enableDinicAlgCorrectnessTests = true;
#endif
	if ( enableDinicAlgCorrectnessTests )
	{
		int dinicACTestsCount = getTestCases4Dinic().size();
		std::cout << dinicACTestsCount << " : ";
		int failsCount = runAllAlgCorrectnessTests( getTestCases4Dinic(), & runAllDinicAlgCorrectnessTest );
		if ( failsCount == 0 )
		{
			std::cout << " \t -- all tests were OK";
		} else
		{
			std::cout << " " << failsCount << " fails ware detected.";
		}
		BOOST_CHECK_EQUAL( 0, failsCount );
	} else
	{
		std::cout << " disabled";
	}
	std::cout << "\n";
}

namespace
{

void runAllMinCostFlowAlgCorrectnessTest( const IGraphGeneratorPtr & generator, int & failsCount, double eps )
{
	try
	{
		IGraphGenerator::GraphPtr agrPtr = generator->generate();
		CostFlowGraph2Gen * grPtr = dynamic_cast< CostFlowGraph2Gen * >( agrPtr.get() );
		BOOST_CHECK( grPtr != NULL );
		CompactNetPtr cnptr = clonegr2compact( * grPtr, true );

		Dinic< CostFlowGraph2Gen > dinic( * grPtr );
		dinic( 0, 1 );
		double maxFlow = dinic.getTotalFlow();

		std::vector< double > flow2test;
//		flow2test.push_back( maxFlow / 3 );
//		flow2test.push_back( maxFlow / 2 );
		flow2test.push_back( 2 * maxFlow / 3 );
//		flow2test.push_back( maxFlow );
		flow2test.push_back( 4 * maxFlow / 3 );
		for ( std::vector< double >::iterator it = flow2test.begin(); it != flow2test.end(); ++it )
		{
			double desiredFlow = * it;
			MinCostFlow< CostFlowGraph2Gen > mcf( * grPtr );
			mcf( 0, 1, desiredFlow );
			double foundFlowA = mcf.getTotalFlow();
			double costA = mcf.getTotalCost();
			std::pair< double, double > smcfRes = stupidMinCostFlowOnCompactNet( * cnptr, 0, 1, desiredFlow, eps );
			double foundFlowB = smcfRes.first;
			double costB = smcfRes.second;
			BOOST_CHECK_CLOSE( foundFlowA, foundFlowB, 1e-5 );
			BOOST_CHECK_CLOSE( costA, costB, 1e-5 );
			if ( theabs( foundFlowA - foundFlowB ) > eps || theabs( costA - costB ) > eps * 2 )
			{
				failsCount++;
			}
		}
	} catch ( ... ) {
		failsCount++;
	}
}

int runAllMinCostFlowAlgCorrectnessTests( double eps = 1e-5 )
{
	std::vector< TestCase > testCases = getTestCases4MinCostFlow();
	int testCasesCount = testCases.size();
	int failsCount = 0;
	for ( int i = 0; i < testCasesCount; i++ )
	{
		IGraphGeneratorPtr generator = testCases[i].first;
		std::cout << ( i == 0 ? " " : "; " ) << generator->getName() << " (" << testCases[i].second << ")";
		std::cout.flush();
		for ( int tcr = 0; tcr < testCases[i].second; tcr++ )
		{
			runAllMinCostFlowAlgCorrectnessTest( generator, failsCount, eps );
		}
	}
	return failsCount;
}

}

void TestMinCostFlowAlgCorrectness()
{
	std::cout << "\tMin-cost-flow algorithm correctness tests: ";
	bool enableDinicAlgCorrectnessTests = false;
	std::vector< TestCase > testCases = getTestCases4MinCostFlow();
#ifdef MCF_ONE_ALG_TESTS
# define MINCOSTFLOW_ALG_TESTS
	for ( std::vector< TestCase >::iterator it = testCases.begin(); it !=  testCases.end(); ++it )
	{
		it->second = 1;
	}
#endif

#ifdef MINCOSTFLOW_ALG_TESTS
	enableDinicAlgCorrectnessTests = true;
#endif
	if ( enableDinicAlgCorrectnessTests )
	{
		int dinicACTestsCount = testCases.size();
		std::cout << dinicACTestsCount << " : ";
		int failsCount = runAllAlgCorrectnessTests( testCases, & runAllMinCostFlowAlgCorrectnessTest );
		if ( failsCount == 0 )
		{
			std::cout << " \t -- all tests were OK";
		} else
		{
			std::cout << " " << failsCount << " fails ware detected.";
		}
		BOOST_CHECK_EQUAL( 0, failsCount );
	} else
	{
		std::cout << " disabled";
	}
	std::cout << "\n";
}
